package 递归与分治算法.最大数组问题;

/**
 * @Project: Data Structure and Algorithms
 * @Package: 递归与分治算法.最大数组问题
 * @ClassName: MaxSubArray
 * @Author: zhouyihe
 * @Date: 2025/11/17 21:16
 * @Description: 最大子数组-动态规划
 * 初始化两个变量：maxSoFar（全局最大和）和 maxEndingHere（以当前位置结尾的最大和）
 * 遍历数组，对每个元素:
 * 更新 maxEndingHere = max(nums[i], maxEndingHere + nums[i])
 * 更新 maxSoFar = max(maxSoFar, maxEndingHere)
 * 返回 maxSoFar 作为结果
 * 优点:
 * 时间复杂度为O(n)，最优解法
 * 空间复杂度为O(1)，只需要常数额外空间
 * 只需要一次遍历数组
 * 实现简单，代码简洁
 * 缺点:
 * 不容易扩展，比如扩展到二维数组的情况
 * 原始版本不能处理"最大子数组必须非空"的约束
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int[] arr1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("最大子数组和: " + maxSubArray(arr1)); // 输出: 6 (子数组 [4, -1, 2, 1])

        int[] arr2 = {1};
        System.out.println("最大子数组和: " + maxSubArray(arr2)); // 输出: 1

        int[] arr3 = {5, 4, -1, 7, 8};
        System.out.println("最大子数组和: " + maxSubArray(arr3)); // 输出: 23 (整个数组)
    }

    private static int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 选择当前元素,看当前元素和当前最大 哪个更大 取大值
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            // 更新全局最大和
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}
